namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0052. N皇后 II")]
    public class No0052_TotalNQueens : AbsBaseTestItem
    {
        /*
        n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
        给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
        每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
        提示：
            皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
            皇后，是国际象棋中的棋子，意味着国王的妻子。皇后只做一件事，那就是“吃子”。当她遇见可以吃的棋子时，就迅速冲上去吃掉棋子。当然，她横、竖、斜都可走一或 N-1 步，可进可退。
        */

        public override void OnTest()
        {
            Assert.TestExe(TotalNQueens, 4, 2);
        }

        public int TotalNQueens(int n)
        {
            int solve(int n, int row, int columns, int diagonals1, int diagonals2)
            {
                if (row == n)
                {
                    return 1;
                }
                int count = 0;
                int availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2));
                while (availablePositions != 0)
                {
                    int position = availablePositions & (-availablePositions);
                    availablePositions = availablePositions & (availablePositions - 1);
                    count += solve(n, row + 1, columns | position, (diagonals1 | position) << 1, (diagonals2 | position) >> 1);
                }
                return count;
            };
            return solve(n, 0, 0, 0, 0);
        }
    }
}
